#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED
#include <ostream>
#include <exception>
#include "List.h"

template <typename T>
struct LinkNode{
public:
    T m_info;
    LinkNode* m_next;

    LinkNode(){
        this->m_next = 0;
    }
};

template <typename T>
std::ostream& operator << (std::ostream& os, const LinkNode<T>& node){
    os<<node.m_info;
    return os;
}

template <typename T>
class LinkedList:public List<T>{
private:
    LinkNode<T>* m_head;
    LinkNode<T>* m_tail;

private:
    bool FindInPosition(int position, LinkNode<T>*& prev, LinkNode<T>*& cur){
        int pos = 0;
        LinkNode<T>* temp = this->m_head->m_next;
        LinkNode<T>* prevtemp = this->m_head;
        while(pos!=position && temp!=0){
            prevtemp = temp;
            temp = temp->m_next;
            pos++;
        }
        if(pos == position){//find it
            prev = prevtemp;
            cur = temp;
            return true;
        }
        prev = 0;
        cur = 0;
        return false;
    }

protected:
    LinkNode<T>* GetHead(){
        return this->m_head;
    }

    LinkNode<T>* GetTail(){
        return this->m_tail;
    }

public:
    LinkedList(){
        try{
            this->m_head = new LinkNode<T>();
        }catch(std::bad_alloc& e){
            this->m_head = 0;
        }
        this->m_tail = this->m_head;
    }

    LinkedList(const LinkedList<T>& linkedlist){
        this->m_head = new LinkNode<T>();
        LinkNode<T>* tempsrc = linkedlist.m_head;
        LinkNode<T>* tempdes = this->m_head;
        while(tempsrc->m_next != 0){
            tempdes->m_next = new LinkNode<T>();
            tempdes= tempdes->m_next;
            tempsrc = tempsrc->m_next;
            tempdes->m_info = tempsrc->m_info;
        }
        this->m_tail = tempdes;
    }

    LinkedList<T>& operator = (const LinkedList< T >& linkedlist){
        this->m_head = new LinkNode<T>();
        LinkNode<T>* tempsrc = linkedlist.m_head;
        LinkNode<T>* tempdes = this->m_head;
        while(tempsrc->m_next!=0){
            tempdes->m_next = new LinkNode<T>();
            tempdes= tempdes->m_next;
            tempsrc = tempsrc->m_next;
            tempdes->m_info = tempsrc->m_info;
        }
        this->m_tail = tempdes;
        return *this;
    }

    virtual ~LinkedList(){
        while(this->m_head!=this->m_tail){
            LinkNode<T>* temp = this->m_head;
            this->m_head = temp->m_next;
            delete temp;
        }
        delete this->m_head;
    }

    virtual void Clear(){
        LinkNode<T>* temp = this->m_head->m_next;
        while(temp!=0){
            LinkNode<T>* temp2 = temp->m_next;
            delete temp;
            temp = temp2;
        }
        this->m_tail = this->m_head;
    }

    virtual bool IsEmpty(){
        return this->m_head == this->m_tail;
    }

    virtual bool Append(const T& value){
        try{
            this->m_tail->m_next = new LinkNode<T>();
            this->m_tail = this->m_tail->m_next;
            this->m_tail->m_info = value;
            return true;
        }catch(std::bad_alloc& e){
            return false;
        }
        return false;
    }

    virtual bool Insert(const int position, const T& value){
        LinkNode<T>* prev = 0;
        LinkNode<T>* cur = 0;
        if(this->FindInPosition(position,prev, cur)){
            try{
                prev->m_next = new LinkNode<T>();
                prev = prev->m_next;
                prev->m_info = value;
                prev->m_next = cur;
                if(cur==0){
                    this->m_tail = prev;
                }
            }catch(std::bad_alloc& e){
                return false;
            }
            return true;
        }
        return false;
    }

    virtual bool Delete(const int position){
        LinkNode<T>* prev = 0;
        LinkNode<T>* cur = 0;
        if(this->FindInPosition(position,prev, cur)){
            if(cur!=0){
                prev->m_next = cur->m_next;
                if(cur->m_next == 0){
                    this->m_tail = prev;
                }
                delete cur;
                return true;
            }
        }
        return false;
    }

    virtual bool GetValue(const int position, T& value){
        LinkNode<T>* prev = 0;
        LinkNode<T>* cur = 0;
        if(this->FindInPosition(position,prev, cur)){
            if(cur!=0){
                value = cur->m_info;
                return true;
            }
        }
        return false;
    }

    virtual bool SetValue(const int position, const T& value){
        LinkNode<T>* prev = 0;
        LinkNode<T>* cur = 0;
        if(this->FindInPosition(position,prev, cur)){
            if(cur!=0){
                cur->m_info = value;
                return true;
            }
        }
        return false;
    }

    virtual bool GetPosition(int& position, const T& value){
        int cnt = 0;
        LinkNode<T>* temp = this->m_head->m_next;
        while(temp!=0){
            if(temp->m_info == value){
                position = cnt;
                return true;
            }
            cnt++;
        }
        return false;
    }

    virtual void DumpList(std::ostream& os){
        if(this->IsEmpty()){
            os<<"This is an empty list."<<"\n";
            return;
        }
        LinkNode<T>* temp = this->m_head->m_next;
        while(temp!=0){
            os<<"["<<*temp<<"]";
            temp = temp->m_next;
        }
        os<<"\n";
    }

};

#endif // LINKEDLIST_H_INCLUDED
